//线性dp-二分
int diff(vector<int>& v) {
	const int len = v.size(), sum = accumulate(v.begin(), v.end(), 0);
	vector<vector<int>> dp(len + 1, vector<int>(sum / 2 + 1, 0));
	for (int i = 1; i <= len; ++i)
		for (int j = 1; j <= sum / 2; ++j) {
			if (j >= v[i - 1])
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i - 1]] + v[i - 1]);
			else
				dp[i][j] = dp[i - 1][j];
		}
	return sum - 2 * dp[len][sum / 2];
}



//线性dp-LIS
int LIS(){
    int ans = 0;
    int n;cin>>n;
    int f[n+1]={0},a[n+1]={0};
    for(int i=1; i<=n; i++) 
    {
        cin>>a[i];
        f[i] = 1;
    }
    for(int i=1; i<=n; i++)
        for(int j=1; j<i; j++)
            if(a[j] < a[i])f[i] = max(f[i], f[j]+1);
    for(int i=1; i<=n; i++) ans = max(ans, f[i]);
    printf("%d\n", ans);
    return 0;
}



//贪心+二分-LIS
const int maxn =300003, INF = 0x7f7f7f7f;
int low[maxn], a[maxn];
int n, ans;
int binary_search(int *a, int R, int x)//二分查找，返回a数组中第一个>=x的位置 
{
    int L = 1, mid;
    while(L <= R)
    {
        mid = (L+R) >> 1;
        if(a[mid] <= x)
            L = mid + 1;
        else 
            R = mid - 1;
    }
    return L;
}
void LIS()
{
    cin>>n;
    for(int i=1; i<=n; i++) 
    {
        cin>>a[i]; 
        low[i] = INF;   //由于low中存的是最小值，所以low初始化为INF 
    }
    low[1] = a[1]; 
    ans = 1;   //初始时LIS长度为1 
    for(int i=2; i<=n; i++)
    {
        if(a[i] > low[ans])    //若a[i]>=low[ans]，直接把a[i]接到后面 
            low[++ans] = a[i];
        else       //否则，找到low中第一个>=a[i]的位置low[j]，用a[i]更新low[j] 
            low[binary_search(low, ans, a[i])] = a[i];
    }
    cout<<ans<<endl;   //输出答案 
}

//线性dp-最大连续子数组和
int MaxSumOfSub(){
    int res=-INF;
    int dp[N];
    dp[0]=0;
    for(int i=1;i<=cnt;i++){
        dp[i]=max(dp[i-1]+nums[i],nums[i]);
        res=max(dp[i],res);
    }
    return res;
}

//线性dp-打家劫舍
int rob(vector<int> nums) {
    if (nums.empty()) {
        return 0;
    }
    int size = nums.size();
    if (size == 1) {
        return nums[0];
    }
    vector<int> dp = vector<int>(size, 0);
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);
    for (int i = 2; i < size; i++) {
        dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
    }
    return dp[size - 1];
}